//
// Description: 42. 接雨水
// Created by Loading on 2021/8/14.
//

#include <bits/stdc++.h>

using namespace std;

int trap(vector<int> &height) {
    // 表示含当前位置的左侧最大高度，右侧最大高度
    vector<int> left_max(height.size()), right_max(height.size());
    int current_max = 0;
    for (int i = 0; i < height.size(); ++i) {
        current_max = max(current_max, height[i]);
        left_max[i] = current_max;
    }
    current_max = 0;
    for (int i = (int) height.size() - 1; i >= 0; --i) {
        current_max = max(current_max, height[i]);
        right_max[i] = current_max;
    }

    int sum = 0;
    // 遍历每个位置，计算每个位置的接水量
    for (int i = 0; i < height.size(); ++i) {
        // 当前位置的接水量 = 两侧最高点的最小值 - 当前位置高度
        sum += min(left_max[i], right_max[i]) - height[i];
    }

    return sum;
}

int main() {
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    int sum = trap(height);
    cout << sum << endl;
}